package 练习;

public class 归并排序
{
    public static void main(String[] args)
    {

    }
    public static void Sort(int[] num)
    {
        int[] temp=new int[num.length];
        sort(num,0,num.length-1,temp);
    }
    public static void sort(int[] num,int left,int right,int[] temp)
    {
        if (left<right)
        {
            int mid=(left+right)/2;
            sort(num,left,mid,temp);
            sort(num, mid+1, right, temp);
            merge(num,left,mid,right,temp);
        }
    }
    public static void merge(int[] num,int left,int mid,int right,int[] temp)
    {
        int i=left;
        int j=right;
        int t=0;
        while (i<=mid&&j<=right)
        {
            if (num[i]<=num[j])
            {
                temp[t++]=num[i++];
                //外部量，count++;
            }
            else
                temp[t++]=num[j++];
        }
        //把剩下的复制过来
        while (i<=mid)
            temp[t++]=num[i++];
        while (j<=right)
            temp[t++]=num[j++];
        t=0;
        while(left<=right)
        {
            num[left++]=temp[t++];
        }
    }
}
